package com.datastructure.test.median;

import java.util.ArrayList;

public class Median {

    public static void main(String[] args) {

    }

    public double Median (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {
        // write code here
        int n = nums1.size();
        int m = nums2.size();
        int[] arr = new int[n + m];
        int i = n - 1;
        int j = m - 1;
        int index = arr.length - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j < 0) {
                arr[index--] = nums1.get(i);
                i--;
                continue;
            }
            if (j >= 0 && i < 0) {
                arr[index--] = nums2.get(j);
                j--;
                continue;
            }
            if (nums1.get(i) >= nums2.get(j)) {
                arr[index--] = nums1.get(i);
                i--;
            } else {
                arr[index--] = nums2.get(j);
                j--;
            }

        }
        if (arr.length % 2 != 0) {
            return arr[arr.length / 2] * 1.0;
        } else {
            int mid = arr[arr.length / 2] + arr[arr.length / 2 - 1];
            return mid / 2.0;
        }
    }
}
